package com.code.leetcode._202507;

//48 旋转图像
public class Rotate {

    /**
     * 给定一个n*n的二维矩阵matrix表示一个图像，请你将图像顺时针旋转90度
     * 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵，请不要使用另外一个矩阵来旋转图像
     * 示例1：输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[[7,4,1],[8,5,2],[9,6,3]]
     * 示例2：输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
     * 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
     **/
    public static void main(String[] args) {

    }

    /**
     * 使用辅助数组
     * 我们以题目中的示例二作为例子，分析将图像旋转90度之后，这些数字出现在什么位置
     * 对于矩阵的第一行而言，在旋转后，他粗线在倒数第一列的位置
     * 并且，第一行的第x个元素在旋转后恰好是出现在倒数第一列的第x个元素
     * 对于矩阵中的第二行而言，在旋转后，它出现在倒数第二列的位置。
     * 对于矩阵中的第三行和第四行同理，这样我们可以得到规律：
     * 对于矩阵中第i行的第j个元素，在旋转后，它出现在倒数第i列的第j个位置
     * 我们将其翻译成代码，由于矩阵中的行列从0开始计数，因此队于矩阵中的元素matrix[row][col]，在旋转后
     * 它的新的位置为matrix new[col][n-row-1]
     * 这样以来，我们使用一个与matrix大小相同的辅助数组matrix new,临时存储旋转后的结果。我们遍历matrix中的
     * 每一个元素，根据上述规则将该元素存放到matrix new中对应的位置。在遍历完成之后，再将matrix new 中的结果
     * 复制到原数组中即可。
     **/
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }

    /**
     * 原地旋转
     * 题目中要求我们尝试不适用额外内存空间的情况下进行矩阵的旋转，也就是说，我们需要 原地旋转 这个矩阵。那么我们如何
     * 在方法一的基础上完成原地旋转呢？
     * 我们观察方法一的关键等式：matrix_new[col][n-row-1] = matrix[row][col]
     * 它阻止了我们进行原地旋转，这是因为如果我们直接将matrix[row][col]放到原矩阵中的目标位置matrix[col][n−row−1]：
     * matrix[col][n−row−1]=matrix[row][col]
     * 原矩阵中的matrix[col][n−row−1] 就被覆盖了!这并不是我们想要的结果。因此我们可以考虑用一个临时变量temp暂存
     * matrix[col][n-row-1]的值，这样虽然matrix[col][n-row-1]被覆盖了，我们还是可以通过temp获取它原来的值：
     * temp = matrix[col][n-row-1]
     * matrix[col][n-row-1] = matrix[row][col]
     * 那么matrix[col][n-row-1]经过旋转操作之后会到哪个位置呢？我们还是使用方法一中的关键等式，不过这次，我们需要将
     * row = col
     * col = n-row-1
     * 带入关键等式，就可以得到：matrix[n−row−1][n−col−1]=matrix[col][n−row−1]
     * 同样的，直接赋值会覆盖掉matrix[n−row−1][n−col−1]原来的值，因此我们还是需要使用一个临时变量进行存储，不过这次，
     * 我们可以直接使用之前的临时变量temp：
     * temp= matrix[n−row−1][n−col−1]
     * matrix[n−row−1][n−col−1]=matrix[col][n−row−1]
     * matrix[col][n−row−1]=matrix[row][col]
     * 我们再重复一次之前的操作，matrix[n−row−1][n−col−1]经过旋转操作之后会到哪个位置呢？
     * row = n-row-1
     * col= n-col-1
     * 带入关键等式，就可以得到：matrix[n−col−1][row]=matrix[n−row−1][n−col−1]
     * 写进去：
     * temp=matrix[n−col−1][row]
     * matrix[row][col]=matrix[n−col−1][row]
     * matrix[n−col−1][row]=matrix[n−row−1][n−col−1]
     * matrix[n−row−1][n−col−1]=matrix[col][n−row−1]
     * matrix[col][n−row−1]=temp
     * 当我们知道了如何原地旋转矩阵之后，还有一个重复的问题在于：我们应该枚举哪些位置(row,col)进行上述的原地交换
     * 操作呢？由于每一次原地交换四个位置，因此：
     * 1、当n为偶数时：我们需要枚举n^2/4=(n/2)*(n/2)个位置，可以将该图形分产四块，以4*4的矩阵为例，保证了不重复、不遗漏
     * 2、当n为奇数时，由于中心的位置经过旋转后位置不变，我们需要枚举(n^2-1)/4=((n-1)/2)*((n+1)/2)个位置，需要换一种
     * 划分的方式，以5*5的矩阵为例：同样保证了不重复、不遗漏，矩阵正中央的点无需旋转。
     **/
    public void rotate1(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

    /**
     * 用翻转代替旋转
     * 我们还可以另辟蹊径，用翻转操作代替旋转操作。我们还是以题目中的示例二作为例子，先将其通过水平轴翻转得到；
     * 再根据主对角线翻转得到：这就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分
     * 元素进行交换，即matrix[row][col] 水平轴翻转 matrix[n−row−1][col]
     * 对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，
     * 即matrix[row][col]主对角线翻转matrix[col][row]
     * 将他们联立即可得到：matrix[row][col]水平轴翻转matrix[n−row−1][col]主对角线翻转matrix[col][n−row−1]
     * 和方法一、方法二中的关键等式：matrix new[col][n−row−1]=matrix[row][col]是一致的。
     ***/
    public void rotate2(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}
